package com.lw.leetcode.sort.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 2146. 价格范围内最高排名的 K 样物品
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/10 17:07
 */
public class HighestRankedKItems {

    public static void main(String[] args) {
        HighestRankedKItems test = new HighestRankedKItems();

        // {{0,1},{1,1},{2,1}}
        int[][] grid = {{1, 2, 0, 1}, {1, 3, 0, 1}, {0, 2, 5, 1}};
        int[] pricing = {2, 5};
        int[] start = {0, 0};
        int k = 3;

        // {{2,1},{1,2}}
//        int[][] grid = {{1, 2, 0, 1}, {1, 3, 3, 1}, {0, 2, 5, 1}};
//        int[] pricing = {2, 3};
//        int[] start = {2, 3};
//        int k = 2;

        // {{2,1},{2,0}}
//        int[][] grid = {{1, 1, 1}, {0, 0, 1}, {2, 3, 4}};
//        int[] pricing = {2, 3};
//        int[] start = {0, 0};
//        int k = 3;

        List<List<Integer>> lists = test.highestRankedKItems(grid, pricing, start, k);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }


    public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {
        PriorityQueue<Long> p = new PriorityQueue<>((a, b) -> Long.compare(b, a));
        int m = grid.length;
        int n = grid[0].length;
        long step = -1;
        LinkedList<Long> queue = new LinkedList<>();
        queue.add((long) start[0] * n + start[1]);
        int[][] arr = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int i = grid[start[0]][start[1]];
        grid[start[0]][start[1]] = 0;
        if (i >= pricing[0] && i <= pricing[1]) {
            p.add((long) start[0] * n + start[1]);
        }

        while (!queue.isEmpty()) {
            long v = queue.pollFirst();
            long s = v >> 40;
            if (s > step) {
                if (queue.size() >= k) {
                    break;
                }
                step = s;
            }
            int index = (int) (v & 0XFFFFF);
            int a = index / n;
            int b = index % n;
            for (int[] ints : arr) {
                int x = a + ints[0];
                int y = b + ints[1];
                if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] == 0) {
                    continue;
                }
                int u = grid[x][y];
                grid[x][y] = 0;
                long next = ((s + 1) << 40) + ((long) u << 20) + x * n + y;
                if (u >= pricing[0] && u <= pricing[1]) {
                    p.add(next);
                    if (p.size() > k) {
                        p.poll();
                    }
                }
                queue.add(next);
            }
        }
        List<List<Integer>> list = new ArrayList<>(k);
        while (!p.isEmpty()) {
            long v = p.poll();
            int index = (int) (v & 0XFFFFF);
            int a = index / n;
            int b = index % n;
            list.add(Arrays.asList(a, b));
        }
        Collections.reverse(list);
        return list;
    }


}
